#ifndef __DEQUE_HPP__
#define __DEQUE_HPP__

#include <iostream>
#include <cassert>

// #define PRINT_INFO

namespace stl_self
{
    // 由此函数可得出每个节点区间是由类型来固定大小的
    inline size_t getNodeBufSize(size_t type_size) { return type_size < 512 ? size_t(512 / type_size) : size_t(1); }

    template <typename Type, typename Reference, typename Pointer>
    struct deque_iterator
    {
        typedef Type *pointer;
        typedef Type **map_pointer;
        typedef deque_iterator<Type, Reference, Pointer> self_type;
        typedef deque_iterator<Type, Type &, Type *> iterator;
        typedef deque_iterator<Type, const Type &, const Type *> const_iterator;

        map_pointer _node;
        pointer _cur;
        pointer _first;
        pointer _last;

        void setNode(map_pointer newNode)
        {
            _node = newNode;
            _first = *_node;
            _last = *_node + getNodeBufSize(sizeof(Type));
        }

        explicit deque_iterator() : _node(nullptr), _cur(nullptr), _first(nullptr), _last(nullptr) {}
        deque_iterator(map_pointer node, pointer cur) : _node(node), _cur(cur), _first(*node), _last(*node + getNodeBufSize(sizeof(Type))) {}
        // iterator转换成const_iterator
        deque_iterator(const iterator &other) : _node(other._node), _cur(other._cur), _first(other._first), _last(other._last) {}

        Reference operator*() const { return *_cur; }
        Pointer operator->() const { return _cur; }
        bool operator==(const self_type &other) const { return _cur == other._cur; }
        bool operator!=(const self_type &other) const { return _cur != other._cur; }
        Reference operator[](size_t n) { return *(*this + n); }

        self_type &operator++() // 前置++
        {
            ++_cur;
            if (_cur == _last)
            {
                setNode(_node + 1);
                _cur = _first;
            }
            return *this;
        }

        self_type operator++(int) // 后置++
        {
            self_type tmp(*this);
            ++*this;
            return tmp;
        }

        self_type &operator--() // 前置--
        {
            if (_cur == _first)
            {
                setNode(_node - 1);
                _cur = _last;
            }
            --_cur;
            return *this;
        }

        self_type operator--(int) // 后置--
        {
            self_type tmp(*this);
            --*this;
            return tmp;
        }

        self_type &operator+=(int n)
        {
            int offset = n + (_cur - _first);
            if (offset >= 0 && offset < getNodeBufSize(sizeof(Type)))
            {
                _cur += n;
            }
            else // offset < 0 || offset > getNodeBufSize()
            {
                int node_offset = offset > 0 ? (offset / getNodeBufSize(sizeof(Type))) : (-((-offset - 1) / getNodeBufSize(sizeof(Type))) - 1);
                setNode(_node + node_offset);
                _cur = _first + (offset - node_offset * getNodeBufSize(sizeof(Type)));
            }
            return *this;
        }

        self_type operator+(int n) const
        {
            self_type tmp(*this);
            tmp += n;
            return tmp;
        }

        self_type &operator-=(int n)
        {
            return *this += (-n);
        }

        self_type operator-(int n) const
        {
            self_type tmp(*this);
            tmp -= n;
            return tmp;
        }

        size_t operator-(const self_type &other) const // 两个迭代器之间的元素个数
        {
            return (getNodeBufSize(sizeof(Type)) * (_node - other._node - 1)) + (_cur - _first) + (other._last - other._cur);
        }

        bool operator<(const self_type &other) const { return _node == other._node ? (_cur < other._cur) : _node < other._node; }
        bool operator>(const self_type &other) const { return other < *this; }
        bool operator<=(const self_type &other) const { return !(other < *this); }
        bool operator>=(const self_type &other) const { return !(*this < other); }

    }; // class deque_iterator

    template <typename Type>
    class deque
    {
    private:
        typedef Type *pointer;
        typedef Type **map_pointer;

    public:
        typedef deque_iterator<Type, Type &, Type *> iterator;
        typedef deque_iterator<Type, const Type &, const Type *> const_iterator;

        iterator begin() { return _start; }
        iterator end() { return _finish; }
        const_iterator begin() const { return _start; }
        const_iterator end() const { return _finish; }
        Type &operator[](size_t n) { return _start[n]; }
        const Type &operator[](size_t n) const { return _start[n]; }

    private:
        map_pointer _map;
        size_t _map_size;
        iterator _start;
        iterator _finish;

        enum
        {
            default_map_size = 8
        };

    private:
        void allocate(size_t n)
        {
            size_t nodes = n / getNodeBufSize(sizeof(Type)) + 1;
            _map_size = std::max((size_t)default_map_size, nodes + 2); // nodes + 2 : 前后端保留一个节点空间
            _map = new pointer[_map_size];
            map_pointer start = _map + (_map_size - nodes) / 2;
            map_pointer finish = start + nodes;
            for (map_pointer cur = start; cur != finish; ++cur)
            {
                *cur = new Type[getNodeBufSize(sizeof(Type))];
            }
            _start.setNode(start);
            _finish.setNode(finish - 1); // cur != finish
            _start._cur = _start._first;
            _finish._cur = _finish._first + n % getNodeBufSize(sizeof(Type));
        }

        void initialize(size_t &n, const Type &value)
        {
            iterator cur = _start;
            while (n--)
            {
                *cur++ = value;
            }
        }

    public:
        explicit deque() : _map(nullptr), _map_size(0), _start(), _finish()
        {
#ifdef PRINT_INFO
            std::cout << "explicit deque()" << std::endl;
#endif
        }

        explicit deque(size_t n, const Type &value = Type())
        {
            allocate(n);
            initialize(n, value);
#ifdef PRINT_INFO
            std::cout << "explicit deque(size_t n, const Type &value = Type())" << std::endl;
#endif
        }

        deque(const deque<Type> &other)
        {
            allocate(other.size());
            iterator this_cur = begin();
            for (iterator cur = other.begin(); cur != other.end(); ++cur)
            {
                *(this_cur.cur()) = *cur;
                ++this_cur;
            }
#ifdef PRINT_INFO
            std::cout << "deque(const deque<Type> &other)" << std::endl;
#endif
        }

        deque(deque<Type> &&other)
        {
            swap(other);
#ifdef PRINT_INFO
            std::cout << "deque(deque<Type> &&other)" << std::endl;
#endif
        }

        ~deque()
        {
            for (int i = 0; i < _map_size; ++i)
            {
                delete[] _map[i];
            }
            delete[] _map;

#ifdef PRINT_INFO
            std::cout << "~deque()" << std::endl;
#endif
        }

        deque<Type> &operator=(const deque<Type> &other)
        {
            if (this != &other)
            {
                allocate(other.size());
                iterator this_cur = begin();
                for (iterator cur = other.begin(); cur != other.end(); ++cur)
                {
                    *(this_cur.cur()) = *cur;
                    ++this_cur;
                }
            }

#ifdef PRINT_INFO
            std::cout << "deque<Type> &operator=(const deque<Type> &other)" << std::endl;
#endif
        }

        deque<Type> &operator=(deque<Type> &&other)
        {
            if (this != &other)
            {
                return swap(other);
            }
#ifdef PRINT_INFO
            std::cout << "deque<Type> &operator=(deque<Type> &&other)" << std::endl;
#endif
        }

        size_t size() const { return _finish - _start; }
        bool empty() const { return _start == _finish; }
        void clear() const { return _finish = _start; }

        void swap(deque<Type> &other)
        {
            std::swap(_map, other._map);
            std::swap(_map_size, other._map_size);
            std::swap(_start, other._start);
            std::swap(_finish, other._finish);
        }

        iterator insert(const_iterator pos, const Type &value = Type())
        {
            assert(pos >= begin() && pos <= end());
            iterator end = _finish - 1; // 随机值地址
            while (end._cur >= pos._cur)
            {
                *(end + 1) = *end;
                --end;
            }
            *(pos._cur) = value;
            ++_finish;
            return iterator(pos._node, pos._cur);
        }

        iterator erase(const_iterator pos)
        {
            assert(pos >= begin() && pos < end());
            if (_start._cur == _finish._cur)
            {
                allocate(0);
            }
            iterator start(pos._node, pos._cur + 1);
            while (start != _finish)
            {
                *(start - 1) = *start;
                ++start;
            }
            --_finish;
            return iterator(pos._node, pos._cur);
        }

        void push_back(const Type &value)
        {
            if (_start._cur == _finish._cur)
            {
                allocate(0);
            }
            insert(end(), value);
        }
        void pop_back() { erase(--end()); }
        const Type &back() const { return *(_finish._cur - 1); }

        void pop_front() { erase(begin()); }
        const Type &front() const { return *(_start._cur); }

    }; // class deque

} // namespace stl_self
#endif // #ifndef __DEQUE_HPP__
